package com.breeze.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Random;

/**
 * 169. 多数元素
 * 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于⌊ n/2 ⌋的元素。
 * <p>
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 * <p>
 * 链接：https://leetcode-cn.com/problems/majority-element
 */
public class LeetCode169 {
    /**
     * 方法一： 哈系表统计次数
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> countMap = new HashMap<>();
        int n = nums.length / 2;
        for (int i = 0; i < nums.length; i++) {
            int count = countMap.getOrDefault(nums[i], 0) + 1;
            if (count > n) {
                return nums[i];
            }
            countMap.put(nums[i], count);
        }
        return -1;
    }

    /**
     * 方法二：排序思路
     * 时间复杂度:O（nlog n）
     * 空间复杂度：O(log n)  logn的栈空间
     */
    public int majorityElement2(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }


    /**
     * 方法三：随机化
     * 因为超过(n/2)的数组下标被众数占据了，这样我们随机挑选一个下标对应的元素并验证，有很大的概率能找到众数。
     * <p>
     * 复杂度分析:
     * <p>
     * 空间复杂度：O(1)
     */
    public int majorityElement3(int[] nums) {
        Random rand = new Random();
        int majorityCount = nums.length / 2;

        while (true) {
            // 随机下标
            int candidate = nums[randRange(rand, 0, nums.length)];
            // 统计下标元素出现个次数
            if (countOccurences(nums, candidate) > majorityCount) {
                return candidate;
            }
        }
    }

    private int randRange(Random rand, int min, int max) {
        return rand.nextInt(max - min) + min;
    }

    private int countOccurences(int[] nums, int num) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }

    /**
     * 方法四：摩尔投票法(Boyer-Moore 投票算法)
     * <p>
     * 思想： 如果我们把众数记为 +1，把其他数记为 -1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。
     * <p>
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    public int majorityElement4(int[] nums) {
        int count = 0;
        int candidate = 0;
        for (int num : nums) {
            // 更换候选人
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }


    public static void main(String[] args) {
        int[] nums = {2, 2, 1, 1, 1, 2, 2};
        LeetCode169 leetCode169 = new LeetCode169();
        System.out.println(leetCode169.majorityElement(nums));
        System.out.println(leetCode169.majorityElement2(nums));
        System.out.println(leetCode169.majorityElement3(nums));
        System.out.println(leetCode169.majorityElement4(nums));
    }
}
